/**
 * 表达式类型
 */
export const ExpresionType = {
  UnaryOperator: 1, // 单元操作符
  BinaryOperator: 2, // 双元操作符
  Parentheses: 3, // 括号，左括号
  ImmediateValue: 4, // 立即数
};
/**
 * 表达式 与
 */
export const ExpAnd = {
  type: ExpresionType.BinaryOperator,
  name: '与',
  code: '&',
  children: undefined,
};
/**
 * 表达式 或
 */
export const ExpOr = {
  type: ExpresionType.BinaryOperator,
  name: '或',
  code: '|',
  children: undefined,
};
/**
 * 表达式 非
 */
export const ExpNot = {
  type: ExpresionType.UnaryOperator,
  name: '非',
  code: '!',
  children: undefined,
};
/**
 * 表达式 括号(将括号也抽象成表达式)
 */
export const ExpParentheses = {
  type: ExpresionType.Parentheses,
  name: '括号',
  code: '(',
  children: [], // 只有括号表达式的 children 可以有数据（即括号里的表达式）
};
/**
 * 表达式 右括号，仅在表达式求值的时候需要用到
 */
export const ExpParenthesesRight = {
  type: ExpresionType.Parentheses,
  name: '括号',
  code: ')',
  children: [], // 只有括号表达式的 children 可以有数据（即括号里的表达式）
};
/**
 * 表达式 立即数(标签编号)
 */
export const ExpImmediateValue = {
  type: ExpresionType.ImmediateValue,
  name: '数字1',
  code: '1',
  children: undefined,
};

export const getRadomExpId = () => {
  // 生成长度为 6 的随机字符串
  const chars = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789';
  let result = '';
  for (let i = 0; i < 8; i++) {
    result += chars.charAt(Math.floor(Math.random() * chars.length));
  }
  return result;
};

/**
 * 将表达式数组展开成一维的
 *
 * @param {Array} list 由操作数、操作符、左括号组成的多维表达式
 * @return {Array}
 */
export function expandExpression(list) {
  // 展开 list
  // 如果是 ImmediateValue，UnaryOperator，BinaryOperator，直接放入 ret 中
  // 如果是 Parentheses（此时必然有 code='('), 递归的展开括号中的子表达式，并且在子表达式展开完成后，添加右括号(ExpParenthesesRight)到 ret 中。
  const ret = [];
  for (const item of list) {
    if (
      item.type === ExpresionType.ImmediateValue ||
      item.type === ExpresionType.UnaryOperator ||
      item.type === ExpresionType.BinaryOperator
    ) {
      ret.push(item);
    } else if (item.type === ExpresionType.Parentheses) {
      ret.push(item);
      const subExpression = expandExpression(item.children);
      ret.push(...subExpression);
      ret.push(ExpParenthesesRight);
    }
  }
  return ret;
}

/**
 *
 * list 中的元素只有 ImmediateValue，UnaryOperator，BinaryOperator，Parentheses 四种类型
 * list 中的元素顺序，就是表达的书写顺序，如：1 或 2 与 (3 或 !4 与 (!5 或 !6 或 7))
 *
 * 对表达式进行求值, 求值过程如下：
 *
 * 〇、在求值过程中，任何 ImmediateValue 元素，其值都是 1
 *
 * 一、分析表达式
 * 1. 如果是操作数，压入操作数栈；
 * 2. 如果是操作符，压入操作符栈；
 * 3. 如果是左括号(code='(')，压入操作符栈；
 * 4. 如果是右括号(code=')')，对操作符栈和操作数栈进行求值，直到从操作符栈中弹出第一个左括号，停止求值，继续分析表达式；
 * 5. 如果表达式分析完了，对操作符栈和操作数栈进行求值；
 *
 * 二、求值
 * 1. 从操作数栈中弹出一个操作符；
 * 2. 如果是 UnaryOperator，从操作数栈中弹出一个操作数，求值，并将求值结果压回操作数栈；
 * 3. 如果是 BinaryOperator，从操作数栈中弹出两个操作数，求值，并将求值结果压回操作数栈；
 *
 * 如果每一次求值都能获取到足够的操作数，并且最后操作符栈为空，操作数栈只有一个元素（即整个表达式求值的结果），说明表达式合法。
 *
 * 特别的，括号里必须有子表达式，如果是空括号（即遇到右括号时，从操作符栈中弹出的第一个操作符就是左括号），也认为表达式是非法的。
 *
 * @param {Array} list 由操作数、操作符、左右括号组成的一维表达式
 * @return {number} 求值结果（如果表达式合法）
 */
export function valueExpression(list) {
  const operandStack = [];
  const operatorStack = [];
  const subExpStart = '_!_'; // 操作数栈隔珊

  const applyOperator = () => {
    const operator = operatorStack.pop();
    if (operator === undefined) {
      throw new Error('invalid expression');
    }
    if (operator.type === ExpresionType.UnaryOperator) {
      const operand = operandStack.pop();
      if (operand === undefined || operand === subExpStart) {
        throw new Error('invalid expression');
      }
      operandStack.push(1); // Unary operator always results in 1
    } else if (operator.type === ExpresionType.BinaryOperator) {
      const rightOperand = operandStack.pop();
      const leftOperand = operandStack.pop();
      if (
        rightOperand === undefined ||
        leftOperand === undefined ||
        rightOperand === subExpStart ||
        leftOperand === subExpStart
      ) {
        throw new Error('invalid expression');
      }
      operandStack.push(1); // Binary operator always results in 1
    }
  };

  for (const item of list) {
    if (item.type === ExpresionType.ImmediateValue) {
      operandStack.push(1);
    } else if (item.type === ExpresionType.UnaryOperator || item.type === ExpresionType.BinaryOperator) {
      operatorStack.push(item);
    } else if (item.type === ExpresionType.Parentheses) {
      if (item.code === '(') {
        operatorStack.push(item);
        operandStack.push(subExpStart);
      } else if (item.code === ')') {
        while (operatorStack.length > 0 && operatorStack[operatorStack.length - 1].code !== '(') {
          applyOperator();
        }
        if (operatorStack.length === 0 || operatorStack.pop().code !== '(') {
          throw new Error('invalid expression');
        }
        if (operandStack.length > 1) {
          // 子表达式求值完后，操作数栈如果有数据，栈顶第二个元素必定是遇到左括号时插入的隔珊
          if (operandStack[operandStack.length - 2] !== subExpStart) {
            throw new Error('invalid expression');
          }
          const subValue = operandStack.pop(); // 子表达式求值结果
          operandStack.pop(); // 隔珊
          operandStack.push(subValue);
        }
      }
    }
  }

  while (operatorStack.length > 0) {
    applyOperator();
  }

  if (operandStack.length === 1 && operatorStack.length === 0) {
    return operandStack[0];
  }

  throw new Error('invalid expression');
}

/**
 * 将表达式转换字符串
 *
 * @param {Array} list 由操作数、操作符、左右括号组成的一维表达式
 * @return {string}
 */
export function stringExpression(list) {
  // 对 list 中的所有元素，采用其 code 属性，用空格拼接成字符串
  if (!list || list.length === 0) {
    return '';
  }
  const codeNotEmpty = x => {
    return x.code && x.code.trim && x.code.trim() !== '';
  };
  if (!list.every(codeNotEmpty)) {
    throw new Error('invalid expression');
  }
  return list.map(item => item.code).join(' ');
}

/**
 * 将字符串还原为表达式列表
 *
 * @param {string} expStr 字符串形式的表达式（表达式是合法的）
 * @return {Array} 表达式列表
 */
export function expressionFromString(expStr) {
  if (!expStr || expStr.trim() === '') {
    return [];
  }

  const tokens = expStr.trim().split(/\s+/);
  const expressionList = [];
  const stack = [];

  for (const token of tokens) {
    switch (token) {
      case '&':
        if (stack.length === 0) {
          expressionList.push({ ...ExpAnd, id: getRadomExpId() });
        } else {
          stack[stack.length - 1].children.push({ ...ExpAnd, id: getRadomExpId() });
        }
        break;
      case '|':
        if (stack.length === 0) {
          expressionList.push({ ...ExpOr, id: getRadomExpId() });
        } else {
          stack[stack.length - 1].children.push({ ...ExpOr, id: getRadomExpId() });
        }
        break;
      case '!':
        if (stack.length === 0) {
          expressionList.push({ ...ExpNot, id: getRadomExpId() });
        } else {
          stack[stack.length - 1].children.push({ ...ExpNot, id: getRadomExpId() });
        }
        break;
      case '(':
        const newParentheses = { ...ExpParentheses, children: [], id: getRadomExpId() };
        if (stack.length > 0) {
          stack[stack.length - 1].children.push(newParentheses); // [左括号引用 A]
        }
        stack.push(newParentheses); // [左括号引用 B]
        break;
      case ')':
        if (stack.length === 0) {
          throw new Error('Mismatched parentheses');
        }
        const completedParentheses = stack.pop(); // 弹出[左括号引用 B]
        if (stack.length === 0) {
          // 最外层右括号
          expressionList.push(completedParentheses);
        }
        break;
      default:
        const immediateValue = { ...ExpImmediateValue, code: token, name: '', id: getRadomExpId() };
        if (stack.length > 0) {
          stack[stack.length - 1].children.push(immediateValue); // [左括号引用 B], 括号里的操作数
        } else {
          expressionList.push(immediateValue); // 括号外的操作数
        }
    }
  }

  if (stack.length > 0) {
    throw new Error('Mismatched parentheses');
  }

  return expressionList;
}
